package pers.qianyu.month_202102.date_20210208;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 100. 相同的树
 * https://leetcode-cn.com/problems/same-tree/
 *
 * @author mizzle rain
 * @date 2021-02-08 17:51
 */
public class IsSameTree {
    public boolean isSameTree(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode p1 = root1, p2 = root2;
        while (p1 != null || p2 != null || !st.isEmpty()) {
            while (p1 != null && p2 != null) {
                st.addLast(p1);
                st.addLast(p2);
                p1 = p1.left;
                p2 = p2.left;
            }
            if (p1 == null && p2 != null || p1 != null && p2 == null) return false;
            TreeNode node1 = st.pollLast();
            TreeNode node2 = st.pollLast();
            if (node1.val != node2.val) return false;
            p1 = node1.right;
            p2 = node2.right;
        }
        return true;
    }
}
